package sorted;

import java.util.Arrays;

public class S04_ShellSort {

    public static void main(String[] args) {
        int[] arr = {5,7,2,3,4,1,6,18,9,10,16,56,34,23,11,12,31,17,15};
        int[] sorted = shellSort(arr);

        System.out.println("排序后的数组为："+ Arrays.toString(sorted));
    }

    public static int[] shellSort(int[] arr) {
        int length = arr.length;
        int n = length / 2;
        while (n>0){

            for (int i = n; i < length; i++) {
                for (int j = i; j > n-1; j-=n) {
                    if (arr[j] > arr[j-n]) break;
                    int temp = arr[j];
                    arr[j] = arr[j-n];
                    arr[j-n] = temp;
                }
            }

            n = n / 2;
        }

        return arr;
    }
}

